#include<bits/stdc++.h>
using namespace std;
long long n,m,dp[2005][2005],a[30][5];
char c[30001],c1;
int main(){
	freopen("hw.in","r",stdin);
	freopen("hw.out","w",stdout);
	scanf("%d",&m);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>c[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>c1;
		scanf("%d",&a[c1-'a'][1]);
		scanf("%d",&a[c1-'a'][2]);
	}
	for(int l=2;l<=n;l++)
	{
		for(int i=1;l+i-1<=n;i++)
		{
			int j=i+l-1;
			dp[i][j]=1e9;
			if(c[i]==c[j])
			{
				dp[i][j]=dp[i+1][j-1];
			}
			{
				dp[i][j]=min(min(min(a[c[i]-'a'][2],a[c[i]-'a'][1])+dp[i+1][j],min(a[c[j]-'a'][2],a[c[j]-'a'][1])+dp[i][j-1]),dp[i][j]) ;
			} 
		}
	
	}
	printf("%d",dp[1][n]);
	return 0;
}

